package test;

public class GenerateParenthesis {
	public List<String> ret;
    public StringBuilder path;
    public int l,r; //统计左，右括号数
    public void dfs(int n){
        if(l+r==2*n){
            ret.add(new String(path.toString()));
            return ;
        }
   
        //添加左括号
        if(l<n){
            path.append("(");
            l++;
            dfs(n);
            path.deleteCharAt(path.length()-1);
            l--;
        }
        
        //添加右括号
        if(l>r){
            r++;
            path.append(")");
            dfs(n);
            path.deleteCharAt(path.length()-1);
            r--;
        }
    }
    public List<String> generateParenthesis(int n) {
        ret=new ArrayList<>();
        path=new StringBuilder();
        l=r=0;
        dfs(n);
        return ret;
    }

}
